package 困难.数学;

import java.util.Map;
import java.util.TreeMap;

/**
 * 给你一个字符串 s 和一个整数 k 。
 * k 子序列指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是 唯一 的，也就是说每个字符在子序列里只出现过一次。
 * 定义 f(c) 为字符 c 在 s 中出现的次数。
 * k 子序列的 美丽值 定义为这个子序列中每一个字符 c 的 f(c) 之 和 。
 * 比方说，s = "abbbdd" 和 k = 2 ，我们有：
 * f('a') = 1, f('b') = 3, f('d') = 2
 * s 的部分 k 子序列为：
 * "abbbdd" -> "ab" ，美丽值为 f('a') + f('b') = 4
 * "abbbdd" -> "ad" ，美丽值为 f('a') + f('d') = 3
 * "abbbdd" -> "bd" ，美丽值为 f('b') + f('d') = 5
 * 请你返回一个整数，表示所有 k 子序列 里面 美丽值 是 最大值 的子序列数目。由于答案可能很大，将结果对 109 + 7 取余后返回。
 * 一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。
 * 注意：
 * f(c) 指的是字符 c 在字符串 s 的出现次数，不是在 k 子序列里的出现次数。
 * 两个 k 子序列如果有任何一个字符在原字符串中的下标不同，则它们是两个不同的子序列。所以两个不同的 k 子序列可能产生相同的字符串。
 */
public class 统计一个字符串的k子序列美丽值最大的数目_2842 {

    public static void main(String[] args) {

        统计一个字符串的k子序列美丽值最大的数目_2842 impl = new 统计一个字符串的k子序列美丽值最大的数目_2842();

        System.out.println(impl.getComb()[3][2]);

    }

    /**
     * 组合数学
     * 例如：aaaabbbbcccc  k = 2
     * 出现次数最多的元素中选 2 个，这里有 3 个并列第一的次数，那么有
     * C(3,2) 种选法，从 3 个里面选 2 个，ab ac bc 3种选法，每种选法
     * 有 4*4 种可能，公式 = 4 的 k 次方 * C(3,2)
     * 例如：aaaabbbbccccddee  k =4
     * a b c 是必须选择的，共有 4*4*4 种可能
     * 剩下的一个有 C(2,1) 种选法，选择 d 或者 e
     * --> 4*4*4*2*2
     */
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        // 相同出现次数的不同字母个数
        TreeMap<Integer, Integer> treeMap = new TreeMap<>((a, b) -> b - a);
        for (int count : counts) {
            treeMap.put(count, treeMap.getOrDefault(count, 0) + 1);
        }
        int[][] comb = getComb();
        long ans = 1;
        while (k > 0) {
            Map.Entry<Integer, Integer> entry = treeMap.pollFirstEntry();
            if (entry == null) {
                return 0;
            }
            if (entry.getValue() >= k) {
                return (int) (((ans * fastPower(entry.getKey(), k) % mod) * (comb[entry.getValue()][k] % mod)) % mod);
            }
            // 注意不能用 ans *= b % mod --> ans = ans * (b % mod)
            ans = ans * fastPower(entry.getKey(), entry.getValue()) % mod;
            k -= entry.getValue();
        }
        // 上面没有返回答案，说明 s 中不同元素数量 < k
        return 0;
    }

    /**
     * 动态规划求 C(n,k) 的组合数，这里只有 26 种字母，从其中选某几个
     * 所以 n = 26 , 0<=k<=26
     * 1，子问题
     * dp[i][j] 表示从 i 个数里面选取 j 个数的组合数是多少
     * 2，状态转移方程
     * 选或者不选择
     * dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
     * 3，初始化值
     * 从 i 个数选取 0 个数的组合数为 1
     * 从 0 个数选取 >1 个数的组合数为 0
     */
    private int[][] getComb() {
        int[][] dp = new int[27][27];
        for (int i = 0; i < 26; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        return dp;
    }

    private int mod = 1000000007;

    // 快速幂
    private long fastPower(long a, long b) {
        if (b == 1) {
            return a;
        }

        long ans = fastPower(a * a % mod, b >> 1);
        if ((b & 1) == 1) {
            ans = ans * a % mod;
        }
        return ans;
    }

}
